from functools import reduce
from bisect import bisect_left

# 有 N 阶楼梯，每次可上一阶或两阶，求有多少种上楼梯的方法
def ways_to_climb(n):
    if n>2:
        return ways_to_climb(n-1) + ways_to_climb(n-2)
    else:
        return n
print(ways_to_climb(10))

# 强盗抢劫一排房间，每个房间都有钱，不能抢劫两个相邻的房间，要求抢的钱最多。数组如：[2,7,9,3,1]
def max_robbery(nums):
    prev, curr = 0, 0
    for num in nums:
        prev, curr = curr, max(prev + num, curr)
    return curr
print(max_robbery([2, 7, 9, 3, 1]))  # 输出应为 12

# 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
def max_subarray_sum(nums):
    current_sum, max_sum = 0, float('-inf')
    for num in nums:
        current_sum = max(current_sum + num, num)   # 更新当前子数组和，选择要么加入当前元素，要么从当前元素开始新的子数组
        max_sum = max(max_sum, current_sum)         # 更新找到的最大子数组和
    return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(nums))  # 输出应为6


# 最长递增子序列（Longest Increasing Subsequence, LIS）问题通常使用动态规划来解决, 给出最长自增子序列, 输入: [10,9,2,5,3,7,101,18]，输出: [2,3,7,101]。
def longest_increasing_subsequence(nums):
    print('....................................longest_increasing_subsequence')
    tails = []
    for num in nums:
        # 使用二分查找找到第一个大于等于num的元素的位置
        pos = bisect_left(tails, num)
        # 如果没有找到比num更大的元素，则扩展tails
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num            # 更新tails，使得长度为pos+1的递增子序列尾部元素尽量小
    return tails  # tails的长度即为最长递增子序列的长度，元素即为一个可行的最长递增子序列
# 测试
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出应为 [2, 3, 7, 101]

# 给定一个，包含非负整数的 m* n 网格。请找出一条，从左上角到右下角的路径。使得路径上，所有数字总和为最小，每次只能向下，或者向右移动一步。
def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    for i in range(1, rows):            # 初始化第一行和第一列
        grid[i][0] += grid[i-1][0]
    for j in range(1, cols):
        grid[0][j] += grid[0][j-1]
    for i in range(1, rows):            # 动态规划填充其余的格子
        for j in range(1, cols):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[-1][-1]

# 测试代码
grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]
print(min_path_sum(grid))  # 输出应为 7

